'''
https://leetcode.cn/problems/target-sum/
'''
from functools import cache
from typing import List


class Solution:
    # 暴力尝试的dp记忆化搜索版本
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)

        @cache
        def f(i, rest):
            if i == n: return rest == 0
            return f(i + 1, rest - nums[i]) + f(i + 1, rest + nums[i])

        return f(0, target)

    # 将数组分为两个集合A,B  A:前面都是正号， B:前面都是负号
    #                       sumAll = sumA + sumB , and sumAll >= (sumA,sumB) >= 0
    # 要使得 sumA-sumB = target => 2sumA = target + sumA+sumbB => sumA = (target+sumAll) / 2
    #       1)target+sumAll 一定要是偶数，
    #                       或者说target与sumAll一定同号，要么都是奇数，要么都是偶数
    #                       因为回到问题，如果不是这样，那么怎么样都凑不到target
    #       2) sumA + sumB = sumAll     =>      sumA <= sumAll      =>      (target+sumAll) / 2 <= sumAll
    #           => target <= sumAll
    def findTargetSumWays2(self, nums: List[int], target: int) -> int:
        n = len(nums)
        sumAll = sum(nums)
        if target % 2 != sumAll % 2:
            return 0
        if abs(target) > sumAll:
            return 0

        # sumA = (target + sumAll) / 2
        # 目标值 =  (target + sumAll) / 2
        # 在数组中选择元素可选可不选
        @cache
        def f(i, rest):
            if i == n: return rest == 0
            if rest < 0: return 0
            return f(i + 1, rest) + f(i + 1, rest - nums[i])

        return f(0, (target + sumAll) // 2)

    # 将上边的dp，改为打表
    def findTargetSumWays3(self, nums: List[int], target: int) -> int:
        n = len(nums)
        sumAll = sum(nums)
        if target % 2 != sumAll % 2:
            return 0
        if abs(target) > sumAll:
            return 0
        rest = (target + sumAll) // 2
        dp = [[0] * (rest + 1) for _ in range(n + 1)]
        dp[n][0] = 1
        # 第一维度依赖后边的，第二维度依赖前边的
        for i in range(n - 1, -1, -1):
            for rest in range(rest + 1):
                dp[i][rest] = dp[i + 1][rest]
                if rest - nums[i] >= 0:
                    dp[i][rest] += dp[i + 1][rest - nums[i]]
        return dp[0][rest]

    # 将上边的dp，改为打表 + 状态压缩
    def findTargetSumWays4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        sumAll = sum(nums)
        if target % 2 != sumAll % 2:
            return 0
        if abs(target) > sumAll:
            return 0
        rest = (target + sumAll) // 2
        A = [0] * (rest + 1)
        A[0] = 1
        # 第一维度依赖后边的，第二维度依赖前边的
        for i in range(n - 1, -1, -1):
            B = A[:]
            for rest in range(rest + 1):
                if rest - nums[i] >= 0:
                    B[rest] += A[rest - nums[i]]
            A = B
        return A[rest]


nums = [1, 1, 1, 1, 1]
target = 3
print(Solution().findTargetSumWays2(nums, target))
